package lcr076;

/*
 *@author wangpeng
 *2025/10/25 15:29
 *@description TODO
 */
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSelect(nums, 0, n - 1, n - k);
    }

    int quickSelect(int[] nums, int l, int r, int k) {
        if (l >= r) return nums[k];
        // 选择中间元素作为pivot，避免最坏情况
        int x = nums[l + (r - l) / 2];
        int i = l - 1;
        int j = r + 1;

        while (i < j) {
            do i++; while (nums[i] < x);
            do j--; while (nums[j] > x);

            if (i < j) {
                //交换
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }

        // 根据k的位置决定递归方向
        if (k <= j) {
            return quickSelect(nums, l, j, k);
        } else {
            return quickSelect(nums, j + 1, r, k);
        }
    }
}